package leetcode.lcsaf.sliding_window_and_double_pointer.sliding_window_variable_length.find_the_shortest_or_smallest;

public class LC1234 {
    /**
     * 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
     * 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
     * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
     * 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
     * 请返回待替换子串的最小可能长度。
     * 如果原字符串自身就是一个平衡字符串，则返回 0。
     */
    public int balancedString(String s) {
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        int m = n / 4;
        int[] cnt = new int['Z'];
        for (char c : charArray) {
            cnt[c]++;
        }
        if (cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m) {
            return 0;
        }
        int left = 0;
        int ans = n;
        for (int right = 0; right < n; right++) {
            cnt[charArray[right]]--;
            while (cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m) {
                ans = Math.min(ans, right - left + 1);
                cnt[charArray[left]]++;
                left++;
            }
        }
        return ans;
    }
}
